package LeetCode.leetcode21MergeSqList;

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode t1 = list1, t2 = list2;
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        while (t1 != null && t2 != null) {
            if (t1.val <= t2.val) {
                tail.next = t1;
                t1 = t1.next;
                tail = tail.next;
            }else {
                tail.next = t2;
                t2 = t2.next;
                tail = tail.next;
            }
        }
        tail.next = t1 == null ? t2 : t1;
        return newHead.next;
    }
}